package questionSolution.Question_322;

public class Solution_1 {
    public int coinChange(int[] coins, int amount) {
        int [] dp = new int[amount+1];
        int res;
        dp[0] = 0;
        for (int i = 1; i <= amount; i++){
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i >= coin){
                    if(dp[i-coin] != -1){
                        min = Math.min(min, dp[i - coin]);
                    }
                }
            }
            if(min == Integer.MAX_VALUE){
                dp[i] = -1;
            }else {
                dp[i] = min + 1;
            }
        }
        res = dp[amount];
        return res;
    }

    static void main() {
        Solution_1 sol = new Solution_1();
        System.out.println(sol.coinChange(new int[]{1}, 0));
    }
}
